package com.zwj.interview.链表;

/**
 * @Author: Zwj
 * @Date: 2022/9/14 22:38
 */
public class 单链表的倒数第K个节点 {

    /**
     * 思路：
     * 1、先让一个指针 p1 指向链表的头节点 head，然后走 k 步
     * 2、现在的 p1，只要再走 n - k 步，就能走到链表末尾的空指针，趁这个时候，再用一个指针 p2 指向链表头节点 head
     * 3、让 p1 和 p2 同时向前走，p1 走到链表末尾的空指针时前进了 n - k 步，
     * p2 也从 head 开始前进了 n - k 步，停留在第 n - k + 1 个节点上，即恰好停链表的倒数第 k 个节点上
     */

    //倒数第 k 个节点就是正数第 n - k + 1 个节点
    ListNode findFromEnd(ListNode head, int k) {
        //处理链表为空的情况
        if (head == null)
            return null;
        ListNode fast = head;
        ListNode slow = head;
        //可能会有k大于链表节点的情况，所以多加个fast != null的判断
        while (fast != null && k-- > 0) {
            fast = fast.next;
        }
        //走到这k还大于0，说明k大于链表长度，自然也就不存在倒数第K个节点的说法
        if (k > 0) {
            return null;
        }
        //二者再同时往前走，fast走到尾部，那么slow就是我们要的节点
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }



}